package data_structures_and_algorithms.sort.learn;

/**
 * @ClassName Code_0912_sortArray
 * @Description: https://leetcode.cn/problems/sort-an-array/
 * @Author: yongliang.ma
 * @Create_time:2022/10/28 09:34
 */
public class Code_0912_sortArray {

    public class QuickSort{
        public int[] sortArray(int[] nums) {
            if (nums == null || nums.length < 2)
                return nums;
            process(nums, 0, nums.length - 1);
            return nums;
        }

        public void process(int[] nums, int L, int R){
            if (L >= R)
                return;
            // 长度为2的数组，partition[0]：等于的第一个数字，partition[1]：等于的最后一个数字
            int[] partition = partition(nums, L, R);
            if (partition[0] > L + 1){
                process(nums, L, partition[0] - 1);
            }
            if (partition[1] < R - 1){
                process(nums, partition[1] + 1, R);
            }
        }

        // 处理分层，以最右边为基准K，小于K的放在左边，等于K的放在中间，大于K的放在右边
        public int[] partition(int[] nums, int L, int R){
            int lessR = L - 1, cur = L, moreL = R, K = nums[R];
            while (cur < moreL){
                if (nums[cur] < K){
                    swap(nums, ++lessR, cur++);
                }else if (nums[cur] == K){
                    cur++;
                }else {
                    // 大于K的情况
                    swap(nums, --moreL, cur);// 这里--moreL需要注意，有写错过 写成moreL--，和lessR一样先移动位置然后交换值
                }
            }
            // 将大于K的第一个位置和K交换
            swap(nums, moreL, R);
            return new int[]{lessR + 1, moreL};
        }

        public void swap(int[] nums, int a, int b){
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }



}
